package vip.zhenzicheng.algorithm.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 桶排序，暂未优化，可以考虑使用IdentityHashMap?
 *
 * @author zhenzicheng
 * @date 2022-06-09 19:57
 */
public class BucketSort {

  public static void main(String[] args) {
    List<Integer> arr = List.of(3, 1, 5, 6, 6, 23, 8, 9, 4, 7);
    List<Integer> newArr = sort(arr, 2);
    System.out.println(newArr);
  }

  public static List<Integer> sort(List<Integer> arr, int bucketCap) {
    if (arr == null || arr.size() < 2) {
      return arr;
    }

    int max = Collections.max(arr);
    int min = Collections.min(arr);
    int bucketCount = (max - min) / bucketCap + 1; // 桶数量

    // 构建桶
    List<List<Integer>> bucketArr = new ArrayList<>(bucketCount);
    List<Integer> resultArr = new ArrayList<>();
    for (int i = 0; i < bucketCount; i++) {
      bucketArr.add(new ArrayList<>());
    }

    Integer num;
    // 将原始数组中的数据分布到桶中
    for (int i = 0, pos; i < arr.size(); i++) {
      num = arr.get(i);
      pos = (num - min) / bucketCap; // 类似于打散到新位置，类似于 CountingSort
      bucketArr.get(pos)
          .add(num);
    }

    for (int i = 0; i < bucketCount; i++) {
      List<Integer> posArr = bucketArr.get(i);
      if (bucketCap == 1) {
        resultArr.addAll(posArr);
      } else {
        if (bucketCount == 1) {
          bucketCap--;
        }
        List<Integer> temp = sort(posArr, bucketCap); // 对这个桶再一次分桶排序
        resultArr.addAll(temp);
      }
    }

    return resultArr;
  }
}
